{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Second Minimum Node In a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSecondMinimumValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中第二小的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为&nbsp;<code>2</code>&nbsp;或&nbsp;<code>0</code>。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。</p>\n",
    "\n",
    "<p>更正式地说，即&nbsp;<code>root.val = min(root.left.val, root.right.val)</code> 总成立。</p>\n",
    "\n",
    "<p>给出这样的一个二叉树，你需要输出所有节点中的&nbsp;<strong>第二小的值 </strong>。</p>\n",
    "\n",
    "<p>如果第二小的值不存在的话，输出 -1 <strong>。</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/15/smbt1.jpg\" style=\"height: 210px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,2,5,null,null,5,7]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最小的值是 2 ，第二小的值是 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/15/smbt2.jpg\" style=\"height: 113px; width: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,2,2]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>最小的值是 2, 但是不存在第二小的值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 25]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li>对于树中每个节点 <code>root.val == min(root.left.val, root.right.val)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [second-minimum-node-in-a-binary-tree](https://leetcode.cn/problems/second-minimum-node-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [second-minimum-node-in-a-binary-tree](https://leetcode.cn/problems/second-minimum-node-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,5,null,null,5,7]', '[2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # 递归维护最小的两个值\n",
    "        res = self.dfs(root)\n",
    "        return res[1] if res[1] != inf else -1\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root.left:\n",
    "            return root.val, inf\n",
    "        l1, l2 = self.dfs(root.left)\n",
    "        r1, r2 = self.dfs(root.right)\n",
    "        return ans if len(ans:=sorted(set([l1, l2, r1, r2]))[:2]) == 2 else ans + [inf]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # firstsmall, secondsmall = root.val, root.val\n",
    "        # if root.left == None:\n",
    "        #     return -1\n",
    "\n",
    "        # def findmin(root, firstsmall, secondsmall):\n",
    "        #     if root.val > firstsmall and root.val < secondsmall:\n",
    "        #         secondsmall = root.val\n",
    "        #     if root.left is not None:\n",
    "        #         secondsmall = min(findmin(root.left, firstsmall, secondsmall), findmin(root.right, firstsmall, secondsmall))\n",
    "        #     return secondsmall\n",
    "                \n",
    "        # if root.left.val > root.right.val :\n",
    "        #     secondsmall = root.left.val\n",
    "        #     secondsmall = min(findmin(root.right, firstsmall, secondsmall), secondsmall)\n",
    "        # elif root.left.val < root.right.val :\n",
    "        #     secondsmall = root.right.val\n",
    "        #     secondsmall = min(findmin(root.left, firstsmall, secondsmall), secondsmall)\n",
    "        # else :\n",
    "        #     secondsmall = root.right.val\n",
    "        #     secondsmall = min(findmin(root.left, firstsmall, secondsmall), secondsmall)\n",
    "\n",
    "        # if secondsmall == firstsmall :\n",
    "        #     return -1\n",
    "        # return secondsmall\n",
    "        if root.left == None :\n",
    "            return -1\n",
    "        \n",
    "        def tobelist(root):\n",
    "            ans = [root.val]\n",
    "            if root.left is not None:\n",
    "                ans += tobelist(root.left)\n",
    "                ans += tobelist(root.right)\n",
    "            return ans\n",
    "        \n",
    "        ans = set(tobelist(root))\n",
    "        ans = sorted(ans)\n",
    "        if len(ans) < 2:\n",
    "            return -1\n",
    "        return ans[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        if not root.left and not root.right:\n",
    "            return -1\n",
    "        # 第二小的值存在于 更小的子节点那一边的子树的第二小的值 或 更大的子节点 之中\n",
    "        l = root.left.val if root.left.val != root.val else self.findSecondMinimumValue(root.left)\n",
    "        r = root.right.val if root.right.val != root.val else self.findSecondMinimumValue(root.right)\n",
    "        return min(l,r) if l != -1 and r!= -1 else max(l,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        import math \n",
    "        self.ans = math.inf\n",
    "        \n",
    "        '''q = [root]\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                node = q.pop(0)\n",
    "                if node.val>root.val:\n",
    "                    ans = min(node.val, ans)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return -1 if ans ==math.inf else ans\n",
    "        '''\n",
    "        def dfs(root,min_val):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val>min_val:\n",
    "                self.ans = min(self.ans, root.val)\n",
    "            dfs(root.left, min_val)\n",
    "            dfs(root.right, min_val)\n",
    "        dfs(root, root.val)\n",
    "        return self.ans if self.ans!=math.inf else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        self.ans = -1\n",
    "        self.val = root.val\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            if self.ans!= -1 and root.val>=self.ans:\n",
    "                return \n",
    "            if root.val>self.val:\n",
    "                self.ans = root.val\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "      # traverse the tree, store all value in set()\n",
    "      # if len(set) == 1: return -1\n",
    "      # return set.sort[1]\n",
    "      cache = set()      \n",
    "\n",
    "      def dfs(node, cache):\n",
    "        if node is None: \n",
    "          return \n",
    "        \n",
    "        cache.add(node.val)\n",
    "\n",
    "        dfs(node.left, cache)\n",
    "        dfs(node.right, cache)\n",
    "      \n",
    "      dfs(root, cache)\n",
    "\n",
    "\n",
    "      cache = list(cache)\n",
    "      cache.sort()\n",
    "      print(f\"cache {cache}\")\n",
    "\n",
    "      if len(cache) <= 1:\n",
    "        return -1\n",
    "\n",
    "      return cache[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # min1 = min2 = float('inf')\n",
    "        # def Traversal(root):\n",
    "        #     if not root: return \n",
    "        #     nonlocal min1, min2\n",
    "        #     if root.val < min1:\n",
    "        #         min1, min2 = root.val, min1\n",
    "        #     elif root.val < min2 and root.val != min1:\n",
    "        #         min2 = root.val\n",
    "        #     Traversal(root.left)\n",
    "        #     Traversal(root.right)\n",
    "        # Traversal(root)\n",
    "        # return min2 if min2 !=float('inf')  else -1\n",
    "\n",
    "        if not root or not root.left:\n",
    "            return -1\n",
    "        left = root.left.val if root.left.val != root.val else self.findSecondMinimumValue(root.left)\n",
    "        right = root.right.val if root.right.val != root.val else self.findSecondMinimumValue(root.right)\n",
    "        return min(left, right) if left != -1 and right != -1 else max(left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        import math \n",
    "        ans = math.inf\n",
    "        q = [root]\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                node = q.pop(0)\n",
    "                if node.val>root.val:\n",
    "                    ans = min(node.val, ans)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return -1 if ans ==math.inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.min = inf\n",
    "        self.secmin = inf\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val < self.min:\n",
    "                self.min, self.secmin = root.val, self.min \n",
    "            elif root.val < self.secmin and root.val > self.min:\n",
    "                self.secmin = root.val\n",
    "            self.findSecondMinimumValue(root.left)\n",
    "            self.findSecondMinimumValue(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.secmin if self.secmin != inf else -1\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans , rootValue = -1 , root.val\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootValue:\n",
    "                ans = node.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: TreeNode) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "\n",
    "        def dfs(node: TreeNode) -> None:\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root and root.left and root.right:\n",
    "            if root.left.val < root.right.val:\n",
    "                return self.min(self.findSecondMinimumValue(root.left), root.right.val)\n",
    "            elif root.left.val > root.right.val:\n",
    "                return self.min(root.left.val, self.findSecondMinimumValue(root.right))\n",
    "            else:\n",
    "                return self.min(self.findSecondMinimumValue(root.left), self.findSecondMinimumValue(root.right))\n",
    "        else:\n",
    "            return -1\n",
    "    def min(self, x, y):\n",
    "        if x == -1:\n",
    "            return y\n",
    "        if y == -1:\n",
    "            return x\n",
    "        return min(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = -1\n",
    "        self.rootval = root.val\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if self.ans == -1 and node.val > self.rootval:\n",
    "                self.ans = node.val\n",
    "            if self.ans != -1 and node.val < self.ans and node.val > self.rootval:\n",
    "                self.ans = node.val\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        if not root:\n",
    "            return -1\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "\n",
    "        def dfs(node: TreeNode) -> None:\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        self.res_second = -1\n",
    "        self.res_first = root.val\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if self.res_second != -1 and root.val >= self.res_second:\n",
    "                return\n",
    "            if root.val > self.res_first:\n",
    "                self.res_second = root.val\n",
    "            \n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res_second\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "\n",
    "        def dfs(node: TreeNode) -> None:\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\r\n",
    "        def find_min(root:TreeNode,low:int):\r\n",
    "            if not root:\r\n",
    "                return -1\r\n",
    "            if root.val>low:\r\n",
    "                return root.val\r\n",
    "            left=find_min(root.left,low)\r\n",
    "            right=find_min(root.right,low)\r\n",
    "            if left<0:\r\n",
    "                return right\r\n",
    "            if right<0:\r\n",
    "                return left\r\n",
    "            return min(left,right)\r\n",
    "        return find_min(root,root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root.left is None and root.right is None:\n",
    "            return -1\n",
    "\n",
    "        left = root.left.val\n",
    "        right = root.right.val\n",
    "\n",
    "        if root.val == root.left.val:\n",
    "            left = self.findSecondMinimumValue(root.left)\n",
    "        if root.val == root.right.val:\n",
    "            right = self.findSecondMinimumValue(root.right)\n",
    "\n",
    "        if left == -1:\n",
    "            return right\n",
    "        if right == -1:\n",
    "            return left\n",
    "        \n",
    "        return min(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        setlist = set()\n",
    "        self.dfs(root, setlist)\n",
    "        if len(setlist) < 2:\n",
    "            return -1\n",
    "        first = +inf\n",
    "        second = +inf\n",
    "        for i in setlist: ## 遍历set中每一个元素\n",
    "            if i <= first: ## 如果当前值小于最小值\n",
    "                second = first \n",
    "                first  = i\n",
    "            elif i <= second:## 如果当前值仅小于第二小的值\n",
    "                second = i\n",
    "        return second\n",
    " \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "    \n",
    "    def dfs(self, root, setlist):\n",
    "        if not root:\n",
    "            return \n",
    "        setlist.add(root.val)\n",
    "        self.dfs(root.left, setlist)\n",
    "        self.dfs(root.right, setlist)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return -1\n",
    "        self.res = -1\n",
    "        self.smallest = root.val\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return        \n",
    "        if root.val > self.smallest:\n",
    "            if self.res == -1 or root.val < self.res:\n",
    "                self.res = root.val\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution: ## 根节点的值为全局最小值\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = -1\n",
    "        self.dfs(root, root.val)\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, root, cur):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.val != cur:\n",
    "            if self.ans == -1:\n",
    "                self.ans = root.val\n",
    "            else:\n",
    "                self.ans = min(self.ans, root.val)\n",
    "            return\n",
    "        self.dfs(root.left, cur)\n",
    "        self.dfs(root.right, cur)\n",
    "\n",
    "        # self.ans = -1\n",
    "        # def dfs(root, cur): ## cur是不变的，就是头结点的值\n",
    "        #     if not root:\n",
    "        #         return\n",
    "        #     ## 每次递归判断的值都是与头节点不相同的值\n",
    "        #     if root.val != cur: ## 叶节点的值是可以与头节点值相同的。找到不与头节点值相同的最小值\n",
    "        #         if self.ans == -1: ## 表示第一次，就先把头节点值传递给ans\n",
    "        #             self.ans = root.val\n",
    "        #         else:\n",
    "        #             ans = min(self.ans, root.val)\n",
    "        #     dfs(root.left, cur)\n",
    "        #     dfs(root.right,cur)\n",
    "        \n",
    "        # dfs(root, root.val)\n",
    "        # return self.ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     setlist = set() ## set() ## 去除重复值，加入值 set.add(element)\n",
    "    #     self.dfs(root, setlist)  ## 深度优先遍历\n",
    "    #     if len(setlist) < 2:\n",
    "    #         return -1\n",
    "    #     first = +inf\n",
    "    #     second = +inf\n",
    "    #     for i in setlist: ## 遍历set中每一个元素\n",
    "    #         if i <= first: ## 如果当前值小于最小值\n",
    "    #             second = first \n",
    "    #             first  = i\n",
    "    #         elif i <= second:## 如果当前值仅小于第二小的值\n",
    "    #             second = i\n",
    "    #     return second\n",
    "    # def dfs(self, root, setlist):\n",
    "    #     if not root:\n",
    "    #         return \n",
    "    #     setlist.add(root.val)\n",
    "    #     self.dfs(root.left, setlist)\n",
    "    #     self.dfs(root.right, setlist)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=[]\n",
    "        def vnode(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val not in ans:\n",
    "                ans.append(root.val)\n",
    "            vnode(root.left)\n",
    "            vnode(root.right)\n",
    "        vnode(root)\n",
    "        ans.sort()\n",
    "        if len(ans)>1:\n",
    "            return ans[1]\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\r\n",
    "        # 1.遍历\r\n",
    "        self.ans = -1\r\n",
    "        self.rootval = root.val\r\n",
    "        self.dfs(root)\r\n",
    "        return self.ans\r\n",
    "\r\n",
    "    def dfs(self, node):\r\n",
    "        if node is None:\r\n",
    "            return \r\n",
    "        if self.ans != -1 and node.val > self.ans:\r\n",
    "            return\r\n",
    "        if node.val > self.rootval: #递归越往树的上层走数值越小\r\n",
    "            self.ans = node.val\r\n",
    "        \r\n",
    "        self.dfs(node.left)\r\n",
    "        self.dfs(node.right)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.lst = []\n",
    "        def dg(root):\n",
    "            if not root.left and not root.right:\n",
    "                self.lst.append(root.val)\n",
    "            if root.left:\n",
    "                dg(root.left)\n",
    "            if root.right:\n",
    "                dg(root.right)\n",
    "            return sorted(self.lst)\n",
    "        res = dg(root)\n",
    "        for i in range(len(res)):\n",
    "            if res[0] != res[i]:\n",
    "                return res[i]       \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root and root.left and root.right:\n",
    "            if root.left.val < root.right.val:\n",
    "                return self.min(self.findSecondMinimumValue(root.left), root.right.val)\n",
    "            elif root.left.val > root.right.val:\n",
    "                return self.min(root.left.val, self.findSecondMinimumValue(root.right))\n",
    "            else:\n",
    "                return self.min(self.findSecondMinimumValue(root.left), self.findSecondMinimumValue(root.right))\n",
    "        else:\n",
    "            return -1\n",
    "    def min(self, x, y):\n",
    "        if x == -1:\n",
    "            return y\n",
    "        if y == -1:\n",
    "            return x\n",
    "        return min(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        global all_value\n",
    "        all_value=[]\n",
    "        self.dfs(root)\n",
    "        all_value.sort()\n",
    "        min_value = all_value[0]\n",
    "        ans =-1\n",
    "        for i in  all_value:\n",
    "            if i !=min_value:\n",
    "                ans =i \n",
    "                break\n",
    "        return ans\n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return \n",
    "        all_value.append(root.val)\n",
    "        self.dfs(root.left)\n",
    "        self.dfs(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.res = []\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def traverse(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            traverse(node.left)\n",
    "            self.res.append(node.val)\n",
    "            traverse(node.right)\n",
    "        traverse(root)\n",
    "        self.res.sort()\n",
    "        temp = self.res[0]\n",
    "        for i in self.res:\n",
    "            if i>temp:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return float('inf')\n",
    "            \n",
    "            if node.val > root.val:\n",
    "                return node.val\n",
    "            \n",
    "            left_min = dfs(node.left)\n",
    "            right_min = dfs(node.right)\n",
    "            \n",
    "            return min(left_min, right_min)\n",
    "        \n",
    "        second_min = dfs(root)\n",
    "        \n",
    "        return -1 if second_min == float('inf') else second_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, root_value = -1, root.val \n",
    "        def dfs(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return \n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return \n",
    "            if node.val > root_value:\n",
    "                ans = node.val\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "      root_val = root.val\n",
    "      res = -1\n",
    "\n",
    "      def dfs(root):\n",
    "        nonlocal res\n",
    "        if not root: return\n",
    "        if res != -1 and root.val >= res:\n",
    "          return\n",
    "        if root.val > root_val:\n",
    "          res = root.val\n",
    "        \n",
    "        dfs(root.left)\n",
    "        dfs(root.right)\n",
    "      \n",
    "      dfs(root)\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\r\n",
    "        ans = inf\r\n",
    "\r\n",
    "        nodes = [root]\r\n",
    "        while nodes:\r\n",
    "            cur = nodes[0]\r\n",
    "            if cur.left:\r\n",
    "                tmp = max(cur.left.val, cur.right.val)\r\n",
    "                if root.val <= tmp < ans:\r\n",
    "                    if tmp != root.val:\r\n",
    "                        ans = tmp\r\n",
    "                    nodes.append(cur.left)\r\n",
    "                    nodes.append(cur.right)\r\n",
    "            nodes = nodes[1:]\r\n",
    "\r\n",
    "        if ans != inf:\r\n",
    "            return ans\r\n",
    "        else:\r\n",
    "            return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def find_sec(node):\n",
    "            if not node:\n",
    "                return float('inf')\n",
    "            if node.val != root.val:\n",
    "                return node.val\n",
    "            else:\n",
    "                return min(find_sec(node.left), find_sec(node.right))\n",
    "\n",
    "        x = find_sec(root)\n",
    "        if x == float('inf'):\n",
    "            return -1\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        min_val = root.val\n",
    "        \n",
    "        def find_min(root, min_val):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val != min_val:\n",
    "                return root.val\n",
    "            if root.left:\n",
    "                if root.left.val == min_val:\n",
    "                    l_min = find_min(root.left, min_val)\n",
    "                else:\n",
    "                    l_min = root.left.val\n",
    "                if root.right.val == min_val:\n",
    "                    r_min = find_min(root.right, min_val)\n",
    "                else:\n",
    "                    r_min = root.right.val\n",
    "            else:\n",
    "                return root.val\n",
    "            if min_val not in [l_min, r_min]:\n",
    "                return min(l_min, r_min)\n",
    "            return max(l_min, r_min)\n",
    "        \n",
    "        second = find_min(root, min_val)\n",
    "        if second != min_val:\n",
    "            return second\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "            dfs(root.left)\n",
    "            return \n",
    "        \n",
    "        dfs(root)\n",
    "        res.sort()\n",
    "        if res[0]==res[-1]:\n",
    "            return -1\n",
    "        x = min(res)\n",
    "        while x in res:\n",
    "            res.remove(x)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        result , value = -1 , root.val\n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            if not root:\n",
    "                return\n",
    "            if result != -1 and root.val >= result:\n",
    "                return\n",
    "            if root.val > value:\n",
    "                result = root.val\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def recur(root):\n",
    "            if root.left:\n",
    "                if root.left.val==self.first_val:\n",
    "                    recur(root.left)\n",
    "                elif root.left.val<self.second_val:\n",
    "                    self.second_val=root.left.val\n",
    "            if root.right:\n",
    "                if root.right.val==self.first_val:\n",
    "                    recur(root.right)\n",
    "                elif root.right.val<self.second_val:\n",
    "                    self.second_val=root.right.val\n",
    "\n",
    "        self.first_val=root.val\n",
    "        self.second_val=10000000000000\n",
    "        recur(root)\n",
    "        if self.second_val==10000000000000:\n",
    "            return -1\n",
    "        return self.second_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def digui(self,root, xxx):\n",
    "        if len(xxx)==0:\n",
    "            xxx.append(root.val)\n",
    "        elif len(xxx)==1:\n",
    "            if root.val< xxx[0]:\n",
    "                xxx.insert(0,root.val)\n",
    "            elif root.val == xxx[0]:\n",
    "                pass\n",
    "            else:\n",
    "                xxx.append(root.val)\n",
    "        else:\n",
    "            if root.val < xxx[0]:\n",
    "                xxx[1]=xxx[0]\n",
    "                xxx[0]=root.val\n",
    "            elif root.val == xxx[0] : pass\n",
    "            else:\n",
    "                if root.val < xxx[1]:\n",
    "                    xxx[1]=root.val\n",
    "        if root.left:\n",
    "            self.digui(root.left, xxx)\n",
    "        if root.right:\n",
    "            self.digui(root.right, xxx)\n",
    "            \n",
    "    def findSecondMinimumValue(self, root):\n",
    "        xxx=[]\n",
    "        self.digui(root, xxx)\n",
    "        if len(xxx)==2:\n",
    "            return xxx[1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        mi = root.val \n",
    "        ans = inf \n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return \n",
    "            if node.val > mi:\n",
    "                ans = min(ans, node.val)\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return \n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return \n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.l = {}\n",
    "        self.set(root)\n",
    "        l = [x for x in self.l.keys()]\n",
    "        self.sort(l, 0, len(l) - 1)\n",
    "        return len(l) > 1 and l[1] or -1\n",
    "\n",
    "    def set(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.l[root.val] = 0\n",
    "        self.set(root.left)\n",
    "        self.set(root.right)\n",
    "    \n",
    "    def sort(self, nums, i, j):\n",
    "        if i >= j:\n",
    "            return\n",
    "        b = i\n",
    "        e = j\n",
    "        r = nums[e]\n",
    "        while b < e:\n",
    "            while b < e and nums[b] < r:\n",
    "                b += 1\n",
    "            if b < e:\n",
    "                nums[e] = nums[b]\n",
    "                e -= 1\n",
    "            while b < e and nums[e] > r:\n",
    "                e -= 1\n",
    "            if b < e:\n",
    "                nums[b] = nums[e]\n",
    "                b += 1\n",
    "        nums[b] = r\n",
    "        self.sort(nums, i, b - 1)\n",
    "        self.sort(nums, b + 1, j) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: TreeNode) -> int:\n",
    "        def dfs(node, min_val, second_min_val):\n",
    "            if not node:\n",
    "                return second_min_val\n",
    "            if node.val < min_val:\n",
    "                min_val, second_min_val = node.val, min_val\n",
    "            elif min_val < node.val < second_min_val:\n",
    "                second_min_val = node.val\n",
    "            left_val = dfs(node.left, min_val, second_min_val)\n",
    "            right_val = dfs(node.right, min_val, second_min_val)\n",
    "            return min(left_val, right_val)\n",
    "        \n",
    "        min_val = root.val\n",
    "        second_min_val = float('inf')\n",
    "        result = dfs(root, min_val, second_min_val)\n",
    "        \n",
    "        return -1 if result == float('inf') else result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = -1\n",
    "\n",
    "    def dfs(self, root, min_v):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        if self.ans != -1 and root.val >= self.ans:\n",
    "            return\n",
    "        if root.val > min_v:\n",
    "            self.ans = root.val\n",
    "        \n",
    "        self.dfs(root.left, min_v)\n",
    "        self.dfs(root.right, min_v)\n",
    "\n",
    "        \n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        min_v = root.val\n",
    "        self.dfs(root, min_v)\n",
    "        return self.ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 最小的数一定是根，层序遍历\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = [] # 模拟单端队列，后入前出规则\n",
    "        q.append(root)\n",
    "        ans = int(1e12)\n",
    "        flag = 1\n",
    "        while (len(q) != 0):\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                node = q[0]\n",
    "                if (node.val != root.val and node.val < ans):\n",
    "                    ans = node.val\n",
    "                    flag = 0\n",
    "                if (node.left is not None):\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "                q.pop(0)\n",
    "        return ans if flag == 0 else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.res = []\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def traverse(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            traverse(node.left)\n",
    "            self.res.append(node.val)\n",
    "            traverse(node.right)\n",
    "        traverse(root)\n",
    "        self.res.sort()\n",
    "        temp = self.res[0]\n",
    "        for i in self.res:\n",
    "            if i>temp:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        x=set()\n",
    "        def mid(node):\n",
    "            if not node:\n",
    "                return\n",
    "            mid(node.left)\n",
    "            x.add(node.val)\n",
    "            mid(node.right)\n",
    "        mid(root)\n",
    "        if len(x)==1:\n",
    "            return -1\n",
    "        x=sorted(list(x))\n",
    "        return x[1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        second_min = set()\n",
    "        if not root:\n",
    "            return -1\n",
    "        def dfs(node):\n",
    "            nonlocal second_min\n",
    "            if not node:\n",
    "                return\n",
    "            second_min.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return second_min\n",
    "        s = dfs(root)\n",
    "        s = sorted(s)\n",
    "        if len(s) == 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return s[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.lis = []\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.func(root, root.val)\n",
    "        return min(self.lis) if self.lis else -1\n",
    "\n",
    "    def func(self, Root, k):\n",
    "        if Root is None:\n",
    "            return None\n",
    "        if Root.val != k:\n",
    "            self.lis.append(Root.val)\n",
    "        else:\n",
    "            self.func(Root.left, k)\n",
    "            self.func(Root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root.left is None and root.right is None:\n",
    "            return -1\n",
    "\n",
    "        left = root.left.val\n",
    "        right = root.right.val\n",
    "\n",
    "        if root.val == root.left.val:\n",
    "            left = self.findSecondMinimumValue(root.left)\n",
    "        if root.val == root.right.val:\n",
    "            right = self.findSecondMinimumValue(root.right)\n",
    "\n",
    "        if left == -1:\n",
    "            return right\n",
    "        if right == -1:\n",
    "            return left\n",
    "        \n",
    "        return min(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: TreeNode) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "\n",
    "        def dfs(node: TreeNode) -> None:\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return\n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = self.dfs(root)\n",
    "        return res[1] if res[1] != inf else -1\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if not root.left:\n",
    "            return root.val, inf\n",
    "        l1, l2 = self.dfs(root.left)\n",
    "        r1, r2 = self.dfs(root.right)\n",
    "        return ans if len(ans:=sorted(set([l1, l2, r1, r2]))[:2]) == 2 else ans + [inf]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        ans=float('inf')\n",
    "        def dfs(node,n):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if node.val>n:\n",
    "                ans=min(node.val,ans)\n",
    "            dfs(node.left,n)\n",
    "            dfs(node.right,n)\n",
    "            \n",
    "        dfs(root,root.val)\n",
    "        return ans if ans!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        setlist = set()\n",
    "        self.dfs(root, setlist)\n",
    "        if len(setlist) < 2:\n",
    "            return -1\n",
    "        first = +inf\n",
    "        second = +inf\n",
    "        for i in setlist: ## 遍历set中每一个元素\n",
    "            if i <= first: ## 如果当前值小于最小值\n",
    "                second = first \n",
    "                first  = i\n",
    "            elif i <= second:\n",
    "                second = i\n",
    "        return second\n",
    " \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "    \n",
    "    def dfs(self, root, setlist):\n",
    "        if not root:\n",
    "            return \n",
    "        setlist.add(root.val)\n",
    "        self.dfs(root.left, setlist)\n",
    "        self.dfs(root.right, setlist)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = -1\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]) -> None:\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if root.val >= self.res and self.res != -1:\n",
    "                return\n",
    "\n",
    "            if root.val > rootValue:\n",
    "                self.res = root.val\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "\n",
    "        rootValue = root.val\n",
    "        dfs(root)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        start = root.val\n",
    "        res = -1\n",
    "\n",
    "        def setMin(num):\n",
    "            nonlocal start, res\n",
    "            if num > start:\n",
    "                res = num if res == -1 else min(res, num)\n",
    "\n",
    "        def search_node(root, start):\n",
    "            setMin(root.val)\n",
    "            if root.left:\n",
    "                if root.left.val == start:\n",
    "                    search_node(root.left, start)\n",
    "                else:\n",
    "                    setMin(root.left.val)\n",
    "            if root.right:\n",
    "                if root.right.val == start:\n",
    "                    search_node(root.right, start)\n",
    "                else:\n",
    "                    setMin(root.right.val)\n",
    "\n",
    "        search_node(root, start)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        tmp = []\n",
    "        def order(p,tmp):\n",
    "            if p:\n",
    "                tmp.append(p.val)\n",
    "                order(p.right,tmp)\n",
    "                order(p.left,tmp)\n",
    "        order(root,tmp)\n",
    "        tmp = sorted(tmp)\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i] != tmp[0]:\n",
    "                return tmp[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.lis = -1\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.func(root, root.val)\n",
    "        return self.lis\n",
    "\n",
    "    def func(self, Root, k):\n",
    "        if Root is None:\n",
    "            return None\n",
    "        if Root.val != k:\n",
    "            if self.lis == -1:\n",
    "                self.lis = Root.val\n",
    "            else:\n",
    "                self.lis = min(self.lis, Root.val)\n",
    "        else:\n",
    "            self.func(Root.left, k)\n",
    "            self.func(Root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        l = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            l.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        ans = sorted(list(l))\n",
    "        return -1 if len(ans) == 1 else ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        min_val=root.val\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return -1\n",
    "            if root.val>min_val:\n",
    "                return root.val\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            if left<0:return right\n",
    "            if right<0:return left\n",
    "            return min(left,right)\n",
    "        return dfs(root)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        root_val = root.val\n",
    "        res = -1\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if res != -1 and res <= node.val:\n",
    "                return\n",
    "\n",
    "            if node.val > root_val:\n",
    "                res = node.val\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, val):\n",
    "            res = root.val\n",
    "            if val == root.val:\n",
    "                res = 10**20\n",
    "            if root.left:\n",
    "                res = min(res, dfs(root.left, val))\n",
    "            if root.right:\n",
    "                res = min(res, dfs(root.right, val))\n",
    "            return res\n",
    "        t = dfs(root, dfs(root, -1))\n",
    "        return -1 if t == 10**20 else t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans , rootvalue = -1 , root.val\n",
    "        \n",
    "        def dfs(node) :\n",
    "            nonlocal ans \n",
    "            if not node :\n",
    "                return \n",
    "            if ans != -1 and node.val >= ans :\n",
    "                return \n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "        \n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = list()\n",
    "        cands = list()\n",
    "        q.append(root)\n",
    "        min_value = root.val\n",
    "        while len(q) != 0:\n",
    "            i = q.pop()\n",
    "            if i.val == min_value:\n",
    "                if i.left is not None:\n",
    "                    q.append(i.left)\n",
    "                    q.append(i.right)\n",
    "            else:\n",
    "                cands.append(i.val)\n",
    "        if len(cands) == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return min(cands)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nums = set()  # 使用集合来保存节点值，以去重\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode]):\n",
    "        if root is not None:\n",
    "            self.nums.add(root.val)  # 添加节点值到集合\n",
    "            self.dfs(root.left)\n",
    "            self.dfs(root.right)\n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return -1\n",
    "        self.dfs(root)\n",
    "        unique_nums = sorted(self.nums)  # 将集合中的值排序\n",
    "        return -1 if len(unique_nums) <= 1 else unique_nums[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root.left:\n",
    "            return -1\n",
    "        left = root.left.val if root.val!=root.left.val else self.findSecondMinimumValue(root.left)\n",
    "        right = root.right.val if root.val!=root.right.val else self.findSecondMinimumValue(root.right)\n",
    "        return min(left,right) if left != -1 and right != -1 else max(left, right) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        start= root.val\n",
    "        self.result = 2**31\n",
    "        self.qianxu(root,start)\n",
    "        if self.result == 2**31:\n",
    "            return -1\n",
    "        else:\n",
    "            return self.result\n",
    "    def qianxu(self,root,start):\n",
    "        if root == None:\n",
    "            return \n",
    "        else:\n",
    "            val = root.val\n",
    "            if val!=start and val < self.result:\n",
    "                self.result = val\n",
    "            self.qianxu(root.left,start)\n",
    "            self.qianxu(root.right,start)\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        m = root.val\n",
    "        def traversal(root, m):\n",
    "            if not root:\n",
    "                return -1\n",
    "            if root.val > m:\n",
    "                return root.val\n",
    "            left = traversal(root.left, m)\n",
    "            right = traversal(root.right, m)\n",
    "            if left == -1 and right == -1:\n",
    "                return -1\n",
    "            elif left > 0 and right > 0:\n",
    "                return min(left, right)\n",
    "            else:\n",
    "                return max(left, right)\n",
    "        return traversal(root, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        rootval = root.val\n",
    "        res = [-1]\n",
    "        \n",
    "        def find(node):\n",
    "            if node.val > rootval and (res[0] == -1 or node.val < res[0]):\n",
    "                res[0] = node.val\n",
    "            \n",
    "            if node.val == rootval and node.left:\n",
    "                    find(node.left)\n",
    "                    find(node.right)\n",
    "        \n",
    "        find(root)\n",
    "\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def cal(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val<=self.minVal:\n",
    "                self.minVal=root.val\n",
    "            elif root.val<self.minVal2:\n",
    "                self.minVal2=root.val\n",
    "            if root.left:\n",
    "                cal(root.left)\n",
    "            if root.right:\n",
    "                cal(root.right)\n",
    "        self.minVal=inf\n",
    "        self.minVal2=inf\n",
    "        cal(root)\n",
    "        return self.minVal2 if self.minVal2!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        a,b=0,[]\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "\n",
    "            if not root:\n",
    "                return \n",
    "            b.append(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        # b.sort()\n",
    "        c=set(b)\n",
    "        c=sorted(list(c))\n",
    "        print(c)\n",
    "\n",
    "        return (list(c)[1]) if len(list(c))>1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = {}\n",
    "\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        if root.val not in self.res:\n",
    "            self.res[root.val] = 0\n",
    "        self.findSecondMinimumValue(root.left)\n",
    "        self.findSecondMinimumValue(root.right)\n",
    "        v = list(self.res.keys())\n",
    "        v.sort()\n",
    "        return v[1] if len(v) > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return -1 \n",
    "        res = -1\n",
    "        root_val = root.val\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return\n",
    "            if res != -1 and root.val >= res:\n",
    "                return\n",
    "            if root.val > root_val:\n",
    "                res = root.val\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root.left is None and root.right is None:\n",
    "            return -1\n",
    "        root_val = root.val\n",
    "        self.res = 2**32\n",
    "        self.found = False\n",
    "        def help(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val>root_val and node.val<self.res:\n",
    "                self.res = node.val\n",
    "            help(node.left)\n",
    "            help(node.right)\n",
    "        \n",
    "        help(root)\n",
    "        return self.res if not self.res == 2**32 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, rootvalue = -1, root.val\n",
    "        \n",
    "        def dfs(node:TreeNode) -> None:\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return \n",
    "            if ans != -1 and node.val >= ans:\n",
    "                return \n",
    "            if node.val > rootvalue:\n",
    "                ans = node.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:\n",
    "        all_values = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node.left != None:\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            all_values.append(node.val)\n",
    "        \n",
    "        dfs(root)\n",
    "        s = set(all_values)\n",
    "        if len(s) < 2:\n",
    "            return -1\n",
    "        return sorted(list(s))[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
